BZOJ3512 DZY Loves Math IV <莫比乌斯反演+杜教筛>

Problem

DZY Loves Math IV

Description

给定，求模的值。

Input

仅一行，两个整数。

Output

仅一行答案。

Sample Input

1	100000 1000000000

Sample Output

857275582

HINT

，。

Source

By Jc
鸣谢杜教

标签：莫比乌斯反演 杜教筛

Solution

杜教筛经典题。

以下解析部分转载自blutrex的题解。

由于很小，考虑枚举，则转化为求

时，为的前缀和，用杜教筛在内求解。
时，若无平方因子，则有

那么

如此，我们只需要一开始将转化为一个无平方因子的数即可。令为所有质因数乘积，则有。

最终答案为，总时间复杂度为。

Code

#include <bits/stdc++.h>
#define MAX_N 2000000
#define P 1000000007
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int cnt, pri[MAX_N+5];
int phi[MAX_N+5], mi[MAX_N+5], s[MAX_N+5];
bool NotPri[MAX_N+5]; map <lnt, lnt> ex, pr;
void init() {
    mi[1] = phi[1] = s[1] = 1;
    for (int i = 2; i <= MAX_N; i++) {
        if (!NotPri[i]) pri[cnt++] = i, phi[i] = i-1, mi[i] = i;
        for (int j = 0; j < cnt; j++) {
            if (i > MAX_N/pri[j]) break; NotPri[i*pri[j]] = true;
            if (i%pri[j]) phi[i*pri[j]] = phi[i]*(pri[j]-1), mi[i*pri[j]] = mi[i]*pri[j];
            else {phi[i*pri[j]] = phi[i]*pri[j], mi[i*pri[j]] = mi[i]; break;}
        }
        s[i] = (s[i-1]+phi[i])%P;
    }
}
lnt S(int n, int m) {
    if (m <= 1) return phi[n*m];
    if (n == 1) {
        if (m <= MAX_N) return s[m];
        lnt &ret = pr[m]; if (ret) return ret%P;
        ret = 1LL*m*(m+1)/2;
        for (int l = 2, r; l <= m; l = r+1)
            r = m/(m/l), ret -= (r-l+1)*S(1, m/l);
        return ret%P;
    }
    lnt &ret = ex[1LL*n*P+m]; if (ret) return ret;
    for (int i = 1; i*i <= n; i++) if (n%i == 0) {
        ret = (ret+1LL*phi[n/i]*S(i, m/i)%P)%P;
        if (i*i != n) ret = (ret+phi[i]*S(n/i, m/(n/i)))%P;
    }
    return ret;
}
int main() {
    int n, m; lnt ans = 0;
    read(n), read(m), init();
    for (int i = 1; i <= n; i++)
        ans = (ans+i/mi[i]*S(mi[i], m)%P)%P;
    return printf("%lld\n", ans), 0;
}